package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8?toCommentId=9121615
 * 来源：牛客网
 *
 * [编程题]机器人的运动范围
 * 热度指数：408201时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 * 示例1
 * 输入
 * 5,10,10
 * 输出
 * 21
 */
public class RobotMove {

    @Test
    public void testMovingCount() {
        System.out.println(movingCount(10, 1, 100));
    }

    //简单数组遍历轻松解决
    public int movingCount(int threshold, int rows, int cols) {

        if (threshold == 0 || rows == 0 || cols == 0) {
            return 0;
        }

        //计算行的位数
        int r = rows - 1;
        int numOfR = 0;
        while (r != 0) {
            r /= 10;
            numOfR++;
        }

        //计算列的位数
        int c = cols - 1;
        int numOfC = 0;
        while (c != 0) {
            c /= 10;
            numOfC++;
        }

        int result = 0;

        boolean[][] access = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int[] rNums = new int[numOfR];
                int[] cNums = new int[numOfC];
                int index = 0, tempI = i, tempJ = j;
                while (tempI != 0) {
                    rNums[index++] = tempI % 10;
                    tempI /= 10;
                }
                index = 0;
                while (tempJ != 0) {
                    cNums[index++] = tempJ % 10;
                    tempJ /= 10;
                }
                int sum = 0;
                for (int k = 0; k < rNums.length; k++) {
                    sum += rNums[k];
                }
                for (int k = 0; k < cNums.length; k++) {
                    sum += cNums[k];
                }
                if (sum <= threshold) {
                    if (i == 0 && j == 0) {
                        access[i][j] = true;
                        result++;
                    } else {
                        if (i - 1 >= 0 && access[i - 1][j] || j - 1 >= 0 && access[i][j - 1]) {
                            access[i][j] = true;
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
}

